Levenshtein distantzia

Levenshtein distantzia, hitzen arteko distantzia edo edizio-distantzia zenbaki bat da hitz batetik abiatuta beste hitz bat lortzeko egin behar diren gutxieneko eragiketen kopurua dena, informazioaren teorian eta informatikan oso erabilia da. Eragiketa horietako bakoitza hiru mota hauetako bat izan behar da: karaktere bat txertatzea, ezabatzea edo ordezkatzea. Distantzia honek Vladimir Levenshtein zientzialari errusiarraren omenez jaso zuen izen hori, 1965ean asmatu zuen distantzia neurtzeko neurri hori. Bi karaktere-kateen arteko antzekotasuna erabili behar duten programetan erabilgarria da, zuzentzaile ortografikoekin esate baterako.^[1]

Adibidez, "eman" eta "emongo" hitzen arteko distantzia 3 da, gutxienez oinarrizko hiru edizio behar baitira batetik abiatuta bestea lortzeko.

1. eman → emon ('a'-ren ordez 'o' jarrita)
2. emon → emong ('g' bat gehitzea bukaeran)
3. emong → emongo ('o' bat gehitzea bukaeran)

Hamming-en distantziaren orokortze gisa ikusi ohi da, luzera bereko kateetarako erabiltzen dena eta eragiketa moduan 'ordezkatzea' soilik hartzen duena. Levenshteinen distantziaren beste orokortze batzuk badira, esate baterako, Damerau-Levenshtein distantzia, bi karaktereen arteko trukea eragiketa bakar gisa hartzen duena.

'Distantzia' ona denez, propietate hauek betetzen ditu (formalki frogatzea zaila den arren):

Dist (A, B) == Dist (B, A)

Dist (A, B) + Dist (B, C)> = Dist (A, C)

1. ↑ Etxeberria Uztarroz, Izaskun. (2016). Lengoaia eta Sistema Informatikoak SailaInformatika FakultateaAldaera linguistikoen normalizazioainferentzia fonologikoa etamorfologikoa erabiliz.. UPV/EHU, 221 or..